package io.zouyalong.algo.leetcode;

import java.util.BitSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 题目地址：https://leetcode-cn.com/problems/jump-game-ii/
 */
public class JumpGame2 {
    public static void main(String[] args) {
        var input = "2,3,1,2,4,4";
        var inst = new JumpGame2();
        var nums = JumpGame2.split(input);
        System.out.printf("Result: %d\n", inst.solution1DP(nums));
        System.out.printf("Result2: %d\n", inst.solution2DPWithBM(nums));
        System.out.printf("Result3, greedy: %d\n", inst.solution3Greedy(nums));
        System.out.printf("Result4, greedy: %d\n", inst.solution4Greedy(nums));
    }

    public static int[] split(String src) {
        var pieces = src.split(",");
        var results = new int[pieces.length];
        for (int i = 0; i < pieces.length; i++) {
            results[i] = Integer.parseInt(pieces[i]);
        }
        return results;
    }

    public int solution1DP(int[] nums) {
        int[][] from = new int[nums.length][];
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j <= i + nums[i] && j < nums.length; j++) {
                if (from[j] == null) {
                    // 最多就从当前 index 开始的后续点可能到达目标 j
                    from[j] = new int[j - i];
                }
                var len = from[j].length;
                from[j][len - (j - i)] = 1;
            }
        }
        int[] minStep = new int[nums.length];
        for (int i = 1; i < nums.length; i++) {
            int min = Integer.MAX_VALUE;
            for (int j = 0; j < from[i].length; j++) {
                if (from[i][j] == 0) {
                    continue;
                }
                min = Math.min(min, minStep[i - (from[i].length - j)] + 1);
            }
            minStep[i] = min;
        }
        return minStep[nums.length - 1];
    }

    public int solution2DPWithBM(int[] nums) {
        BitSet[] from = new BitSet[nums.length];
        int[] minStep = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            if (i > 0) {
                minStep[i] = Integer.MAX_VALUE;
            }
            for (int j = i + 1; j <= i + nums[i] && j < nums.length; j++) {
                if (from[j] == null) {
                    // 最多就从当前 index 开始的后续点可能到达目标 j
                    from[j] = new BitSet(j - i);
                }
                var len = from[j].size();
//                from[j][len-(j-i)] = 1;
                from[j].set(len - (j - i));
            }
            for (int j = 0; from[i] != null && j < from[i].size(); j++) {
                if (!from[i].get(j)) {
                    continue;
                }
                minStep[i] = Math.min(minStep[i], minStep[i - (from[i].size() - j)] + 1);
            }
        }
        return minStep[nums.length - 1];
    }

    public int solution4Greedy(int[] nums) {
        int n = nums.length;
        int[] f = new int[n];
        for (int i = 1, last = 0; i < n; i++) {
            while (last < n && last + nums[last] < i) last++;
            f[i] = f[last] + 1; // 使用第一个能到i的点更新f[i]
        }
        return f[n - 1];
    }


    public int solution3Greedy(int[] nums) {
        var steps = new LinkedList<Integer>();
        for (int i = 0; i < nums.length - 1; ) {
            int currentEnd = Math.min(i + nums[i], nums.length - 1);
            int maxTarget = currentEnd; // 初始最远距离为直接取当前值跳
            int maxIndex = i;
            for (int j = i + 1; j < currentEnd; j++) {
                // 不包含等于是因为如果两种方式能达到的距离是一样的，那中间跳一次会增加步数，没有收益
                if (j + nums[j] > maxTarget) {
                    maxTarget = j + nums[j];
                    maxIndex = j;
                }
            }
            if (i != maxIndex) {
                steps.offer(maxIndex);
                i = maxIndex;
            } else {
                i = maxTarget;
                steps.offer(maxTarget);
            }
        }
        return steps.size();
    }
}
